package me.sealer.algorithm.search;

/**
 * @author sealer
 * Created on 17/03/02.
 */
public class BinarySearch {
    /**
     * 二分查找
     *
     * @param array
     * @param target
     * @return
     */
    public static int binarySearch(int[] array, int target) {
        int min = 0;
        int max = array.length - 1;
        while (min <= max) {
            //采用无符号右移一位，即可以表示除以2
            int mid = (min + max) >>> 1;
            int midValue = array[mid];
            if (midValue > target) {
                max = mid - 1;
            } else if (array[mid] < target) {
                min = mid + 1;
            } else {
                return mid;
            }

        }
        //没有找到就返回一个与最终位置有关的负数
        return -(min + 1);

    }
    /**
     * binarySearchWithRecursion
     * @param array
     * @param target
     * @param low
     * @param high
     * @return
     */
    private static int binarySearchWithRecursion(int[] array, int target, int low, int high) {
        if (low <= high) {
            int mid = (low + high) / 2;
            if (target == array[mid]) {
                return mid;
            } else if (target > array[mid]) {
                return binarySearchWithRecursion(array, target, mid + 1, high);
            } else {
                return binarySearchWithRecursion(array, target, low, mid - 1);
            }
        }
        return -1;
    }

    /**
     * 二分查找的递归实现
     * 该方法再封装一层， binarySearchWithRecursion(int[] array, int target);
     *
     * @param array
     * @param target
     * @return
     */
    public static int binarySearchWithRecursion(int[] array, int target) {
        if (array == null || array.length == 0) {
            return -1;
        }
        return binarySearchWithRecursion(array, target, 0, array.length - 1);
    }
}
